//给你一个整数数组 cookies ，其中 cookies[i] 表示在第 i 个零食包中的饼干数量。另给你一个整数 k 表示等待分发零食包的孩子数量，所有 
//零食包都需要分发。在同一个零食包中的所有饼干都必须分发给同一个孩子，不能分开。 
//
// 分发的 不公平程度 定义为单个孩子在分发过程中能够获得饼干的最大总数。 
//
// 返回所有分发的最小不公平程度。 
//
// 
//
// 示例 1： 
//
// 输入：cookies = [8,15,10,20,8], k = 2
//输出：31
//解释：一种最优方案是 [8,15,8] 和 [10,20] 。
//- 第 1 个孩子分到 [8,15,8] ，总计 8 + 15 + 8 = 31 块饼干。
//- 第 2 个孩子分到 [10,20] ，总计 10 + 20 = 30 块饼干。
//分发的不公平程度为 max(31,30) = 31 。
//可以证明不存在不公平程度小于 31 的分发方案。
// 
//
// 示例 2： 
//
// 输入：cookies = [6,1,3,2,2,4,1,2], k = 3
//输出：7
//解释：一种最优方案是 [6,1]、[3,2,2] 和 [4,1,2] 。
//- 第 1 个孩子分到 [6,1] ，总计 6 + 1 = 7 块饼干。 
//- 第 2 个孩子分到 [3,2,2] ，总计 3 + 2 + 2 = 7 块饼干。
//- 第 3 个孩子分到 [4,1,2] ，总计 4 + 1 + 2 = 7 块饼干。
//分发的不公平程度为 max(7,7,7) = 7 。
//可以证明不存在不公平程度小于 7 的分发方案。
// 
//
// 
//
// 提示： 
//
// 
// 2 <= cookies.length <= 8 
// 1 <= cookies[i] <= 10⁵ 
// 2 <= k <= cookies.length 
// 
// Related Topics位运算 | 数组 | 动态规划 | 回溯 | 状态压缩 
//
// 👍 44, 👎 0 
//
//
//
//

package leetcode.editor.cn;

import java.util.Arrays;

class FairDistributionOfCookies {
    public static void main(String[] args) {
        Solution solution = new FairDistributionOfCookies().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        int[] bucket;
        int ans = Integer.MAX_VALUE;

        // 和698一致，划分子集的问题
        public int distributeCookies(int[] cookies, int k) {
            // 技巧：先发饼干较多的包，这样让回溯过程更快。下面的回溯代码是从最后一个饼干包开始发所以这里是从小到大排序
            Arrays.sort(cookies);

            this.bucket = new int[k];
            backTracking(cookies, cookies.length - 1, k);
            return ans;
        }

        public void backTracking(int[] cookies, int i, int k) {
            // 饼干包发完了，此时统计那个人饼干最多
            if (i < 0) {
                // 记录一次划分的最大值
                int max = Integer.MIN_VALUE;
                for (int b : bucket) {
                    max = Math.max(max, b);
                }

                // 记录所有划分最大值的最小值
                ans = Math.min(ans, max);
                return;
            }

            // 剪枝1：如果剩下的饼干包不够划分，直接返回
            int count = 0;
            for (int b : bucket) {
                if (b == 0) count++;
            }
            if (i + 1 < count) return;

            // 剪枝2：如果某位小朋友的饼干数量比当前的答案还多，显然继续回溯下去也无法成为最优答案，直接返回
            for (int b : bucket) {
                if (b > ans) return;
            }

            for (int j = 0; j < k; j++) {
                // 剪枝3：第一个饼干包发给谁递归树都是一致的，所以就发送给第一个人
                if (i == cookies.length - 1 && j > 0) continue;
                // 剪枝4：如果元素和相等，那么当前球选择上一个桶和选择当前桶可以得到的结果是一致的
                if (j > 0 && bucket[j] == bucket[j - 1]) continue;
                bucket[j] += cookies[i];
                backTracking(cookies, i - 1, k);
                bucket[j] -= cookies[i];
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
